個人的な再帰関数を書くときのポイント

たまに、関数内部で自身を呼び出すような関数に出会う機会があるかと思います。それは再帰関数と呼ばれ、自分自身を内部で呼び出すことによってループのように振る舞います。そんな再帰関数を書くときの個人的なポイントを整理してみました。

#Python

アシ

2023.07.31

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

再帰関数について

再帰関数は、自分自身を呼び出す関数のことを指します。自分自身を呼び出す事によってある種のループのように振る舞います。

いくつかのアルゴリズムでは再帰を使うことによってシンプルにかける場合があると個人的には思っています。

具体例（フィボナッチ数列）

以下は再帰を用いてN番目のフィボナッチ数列を生成する関数です。フィボナッチ数列は1, 1, 2, 3, 5, 8...のような２個づつ数字を足していくような数列です。

def fibonacci_recursive(n):
    # ここが終了条件になる
    if n == 1 or n == 2:
        return 1

    # ここでfibonacci_recursiveを呼び出す
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

この関数のフローチャートとしては以下のようになります。

N番目のフィボナッチ数列を求めるためにはN-1個目とN-2個目の値が必要になるので、それを自分自身を利用して求めているといった感じです。フィボナッチ数列は1,2番目は１を返すのでそこを条件文を使用し、再帰的に関数が呼び出されないように止めています。

ループで書くと以下のようになります。

def fibonacci_loop(n):
    if n == 1 or n == 2:
        return 1

    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr

    return curr

再帰関数とループの比較

いくつかの観点から再帰関数とループを比較してみます。

構造:
- 再帰関数: 関数が自身の定義を使用して、自身を呼び出す形式で問題を解決します。
- ループ: 制御構造を使用して、同じコードブロックを繰り返し実行して問題を解決します。
コードの可読性:
- 再帰関数: 再帰呼び出しにより、コードが簡潔で自然な場合がありますが、理解が難しいことがあるため、適切なコメントや説明があるといいです。
- ループ: 明確な制御構造により、コードの可読性が高く、理解しやすい傾向があります。
メモリ使用:
- 再帰関数: Pythonの場合は各再帰呼び出しでスタックにフレームが積まれるため、再帰深度が深い場合、メモリ消費が増えます。また、Pythonでは再帰回数に上限があります。
- ループ: 通常、メモリの使用量は再帰関数よりも少なくなります。
適用範囲:
- 再帰関数: 問題を小さなサブ問題に分割する場合や、再帰的な構造が明確な場合に適しています。
- ループ: 同じ操作を繰り返す場合や、明確な制御フローが必要な場合に適しています。

どちらが優れているというわけではなく、ケースによって使い分けることが大切です。再帰のほうがきれいに書ける場合もあれば、ループのほうがきれいに書ける場合もあります。

個人的にはWhile文を使うようなケースで、変数の数が少なく、ループが深くない場合に再帰を使うことが多いです。

再帰関数を書くためのポイント

個人的な再帰関数を書くポイントは以下のとおりです。

１. パラメータをリストアップする:

再帰関数では関数の引数がループにおける状態を保存する変数の役割を持ちます。どの情報を次の呼び出しに使用する必要があるのかを整理しておくと書きやすいです。

２. ベースケースを定義する:

ループの場合終了条件を指定するかと思います。

再帰関数では再帰がストップするような条件をベースケースと呼びます。ベースケースは再帰呼び出しを行わず、結果を直接返す場合に該当します。このベースケースが曖昧だと、無限ループが起きることが多いです。

3. その他の処理のケースを定義する:

ベースケース以外の条件を定義します。ここでは関数を再帰的に呼び出すことになるので、呼び出すパラメータに注意を払いながら、呼び出すようにします。

4. メモ化を考慮する:

再帰関数は、同じ引数で同じ計算を何度も行う場合があります。このような場合には、メモ化を検討して結果を一度計算したら保存して再利用することで、効率的な再帰処理が可能になります。

つまりは、重複した処理を避けるためにキャッシュのような構造を関数に入れておくと便利です。

実際に書いてみる

N番目のフィボナッチ数列を返すような関数を先程のポイントを踏まえながら考えてみます。

１. パラメータをリストアップする:

引数としてNが与えられ、数列をどんどん遡っていくような処理になっています。

なので、次の呼び出しに際して使用したい情報はNになります。この変数が、再帰がいまどの状態にあるのかを保持します。

def fibonacci_recursive(n):

２. ベースケースを定義する:

フィボナッチ数列では以下のような条件があればいいです。フィボナッチ数列では２個前までの値が必要になるので、はじめの２つの値の条件と返り値を書いておきます。 * N=1のときに１を返す * N=2のときに１を返す

def fibonacci_recursive(n):
    # ここが終了条件になる
    if n == 1 or n == 2:
        return 1

3. その他の処理のケースを定義する:

ベースケースの定義が終わったので、再帰する場合の処理を書いていきます。フィボナッチ数列はN-1とN-2個目の値を足し合わせるので、以下のようになります。

fibonacci_recursive(n - 1)とfibonacci_recursive(n - 2)はそれぞれ、N-1とN-2個目の値を返すのでわかりやすいですね。

def fibonacci_recursive(n):
    # ここが終了条件になる
    if n == 1 or n == 2:
        return 1

    # ここでfibonacci_recursiveを呼び出す
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

4. メモ化を考慮する:

さて、今までの３つのステップで関数は動くようになったので少し最適化してみます。

N-1個目の値を計算する過程でN-2個目も必然的に計算する必要があります。ですが、実装ではそれぞれ呼び出しているので計算に重複が生じて非効率的です。キャッシュ構造を入れてあげましょう。

今回はfunctoolsのcacheデコレータを使用します。これは一度呼ばれたときに引数と返り値をメモリ上に保存しておき、再度呼び出されたときはキャッシュから値を返すようにするデコレータです。

import functools

# 返り値をキャッシュ
@functools.cache
def fibonacci_recursive(n):
    # ここが終了条件になる
    if n == 1 or n == 2:
        return 1

    # ここでfibonacci_recursiveを呼び出す
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

Nの値が大きくなると効果が出てきます。